package com.gxc.array;

/**
 * 2552. 统计上升四元组
 * 给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
 *
 * 如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
 *
 * 0 <= i < j < k < l < n 且
 * nums[i] < nums[k] < nums[j] < nums[l] 。
 */
public class CountQuadruplets {

    public long handle(int[] nums) {
        int n = nums.length;
        long res = 0;
        //当前 x ，数组 x 之前的数字 小于 x 的统计
        int[] prevLess = new int[n+1];
        for (int j = 0; j < n; j++) {
            int sum = 0;
            for (int k = n-1; k > j; k--) {
                if (nums[j] > nums[k]) {
                    res += (long) prevLess[nums[k]] * sum;
                } else {
                    //右侧比 nums[j]大的直接不作为 k，作为 l
                    sum++;
                }
            }

            for (int i = nums[j]+1; i <= n; i++) {
                prevLess[i]++;
            }
        }
        return res;
    }

    /**
     * 其实总结一下：就是在一条空白的数轴上，固定一个J点，
     * 然后移动J点右边的K点，统计J点左边总共有几个满足条件的I点，
     * 再统计K点右边有几个满足条件的L点。
     * 当nums[k] < nums[j]时，认为所有条件都达成，
     * 此时可以把两边统计的数用乘法原理算一下，加在ans上。
     * 当K点移动完了以后，再移动J点，直到J点将数轴遍历完。最后返回ans。
     */
    class Solution {
        public long countQuadruplets(int[] nums) {
            int n = nums.length;
            int[] pre = new int[n + 1];
            long ans = 0;
            for (int j = 0; j < n; ++j) {
                int suf = 0;
                for (int k = n - 1; k > j; --k) {
                    if (nums[j] > nums[k]) {
                        ans += (long) pre[nums[k]] * suf;
                    } else {
                        ++suf;
                    }
                }
                //巧妙的计算，每个值之前的小于该值的元素数量
                for (int x = nums[j] + 1; x <= n; ++x) {
                    ++pre[x];
                }
            }
            return ans;
        }
    }

}
